#!/usr/bin/python3
# _*_ coding: utf-8 _*_
#
# Copyright (C) 2024 - 2024 heihieyouheihei, Inc. All Rights Reserved 
#
# @Time    : 2024/9/9 11:11
# @Author  : Yuyun
# @File    : 最大子序列和.py
# @IDE     : PyCharm


"""
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释:  连续子数组  [4,-1,2,1] 的和最大，为  6。
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [5,4,-1,7,8]
输出：23
提示：
1 <= nums.length <= 105
-104 <= nums[i] <= 104
"""

class Solution:
    """
    贪心算法实现
    局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。
    全局最优：选取最大“连续和”
    """
    def max_sublist_sum(self, nums):
        max_result = nums[0]  #存储最大和
        max_sublist= []    #存储和序列
        max_sublist_index = []  #首尾存储区间下标
        length = len(nums)
        tmp_sum = 0
        for i in range(length):
            tmp_sum += nums[i]
            #   取区间累计的最大值（相当于不断确定最大子序终止位置）
            if tmp_sum >= max_result:
                max_sublist_index.append(i)
                max_result = tmp_sum
            #   相当于重置最大子序起始位置，因为遇到负数一定是拉低总和
            if tmp_sum <= 0:
                max_sublist_index.clear()
                tmp_sum = 0
        #   中间可能存在负数，故仅存储正数下标
        for i in range(max_sublist_index[0], max_sublist_index[-1] + 1):
            max_sublist.append(nums[i])

        return max_result, max_sublist
    def max_sum_greedy(self, nums):
        result = nums[0]
        cur_sum = 0
        max_list =[]
        for x in nums:
            cur_sum += x
            if cur_sum > result:
                max_list.append(x)
                result = cur_sum
            if cur_sum <= 0:
                max_list = []
                cur_sum = 0
        return result, max_list

    """
    动态规划解法
    dp[i]表示i个元素前的最大连续和
    dp[i] = max(dp[i - 1] + nums[i], nums[i])
    """
    def max_sum_dp(self, nums):
        if len(nums) == 0:
            return 0
        dp = [None] * len(nums)
        result = dp[0] = nums[0]
        for i in range(1, len(nums)):
            dp[i] = max(dp[i - 1] + nums[i], nums[i])
            result = max(result, dp[i])
        return result
    """
    暴力解法
    """

    def max_sum_violence(self, nums):
        result = nums[0]
        for i in range(len(nums)):
            cur_sum = 0
            for j in range(i, len(nums)):
                cur_sum += nums[j]
                result = max(result, cur_sum)  # 更新最大值
        return result
if __name__ == "__main__":
    nums = list(map(int, input().split(',')))
    solution = Solution()
    result, list_1 = solution.max_sublist_sum(nums)
    print(result, list_1)
